'''
https://leetcode.cn/problems/stickers-to-spell-word/description/
'''
from collections import deque, Counter, defaultdict
from typing import List


class Solution:

    def minStickers(self, stickers: List[str], target: str) -> int:
        n = len(stickers)
        graph = defaultdict(set)

        for i in range(n):
            for char in stickers[i]:
                graph[char].add(stickers[i])
        for char in target:
            if not graph[char]: return -1

        q = deque()
        q.append(target)
        ans = 0
        while q:
            ans += 1
            for _ in range(len(q)):
                target_list = q.popleft()
                # 剪枝，能对首位进行帮助的sticker，我就提出来，因为首位迟早要消
                for sticker in graph[target_list[0]]:
                    res_counter = Counter(target_list) - Counter(sticker)
                    # 没必要再转为字符了，api不冲突
                    rest_target = [char for char, times in res_counter.items() for _ in range(times)]
                    q.append(rest_target)
                    if not rest_target:
                        return ans
        return ans

stickers = ["these","guess","about","garden","him"]
target = "atomher"
print(Solution().minStickers(stickers, target))